Not Applicable.
Not Applicable.
Not Applicable.
This invention relates to verification methods for electronic circuit designs"" functional correctness using a computer program.
A digital circuit includes gates, registers and wires connecting the gates and registers. When people make a large digital circuit design, they write the design in a hardware description language. IEEE standards 1076 and 1364 are 2 well-known hardware description languages. For the purpose of avoiding erroneous chips, they have to verify that the design is functionally correct before transforming the design into a format used for fabricating the chip. As chips growing larger and larger, the existing verification methods are no longer able to guarantee their function correctness.
A method to verify functional correctness is to use a simulator. The simulator reads the circuit design and a set of stimulus values for the inputs of the circuit design. The simulator then computes the circuit design""s response behavior. The circuit design""s functional correctness is decided by comparing the computed response behavior with the expected behavior. These stimulus values are usually supplied in test benches. After the simulator is started, it can read only one test bench, and each test bench supplies only one stimulus value for any input of the circuit design unless the simulator advances the time. The simulator has to be started again before using a different test bench. Each run can only handle only one case while the circuit is designed to handle numerous different cases. This method can handle nearly all practical cases but it is not efficient because too many simulation runs are required for a large design and a lot of computation in the simulator is repeated too many times.
Another method to verify functional correctness is to use a model checker. The model checker reads the circuit design and a statement written in a temporal logic language. The model checker determines whether the statement exactly describes a property of the circuit design. It does this by first computing the state space and then verifying the property against the state space. The circuit design is functionally correct if the model checker gives a positive answer. This method is efficient but it does not work for large circuit designs because its memory requirement for the executing computer is often exponentially proportional to the circuit design""s size, and this problem often happens in the step of computing the state space.
Some symbolic simulation methods also exist. They propagate expressions through gates and registers. These expressions can easily become too large for any computer to handle. These big expressions may not all be needed because often some outputs are not compared against the expectation.
Some hardware methods also exist for functional verification. They are much more expensive than the above software methods, and their efficiency is limited due to the limitation of hardware complexities.
Minimization methods for sequential machines were invented to reduce the size of a digital circuit design during synthesis process without changing the circuit""s behavior, but they were not applied to functional verification before because (1) synthesis and functional verification have different minimization goals and (2) they traditionally use different subsets of hardware description languages.
Automatic test pattern generation (ATPG) methods for non-scan sequential machines were invented known to generate test sequences for detecting stuck-at-1 and stuck-at-0 faults that can happen after the digital circuits are fabricated, but they were not applied to functional verification before.
Changing digital circuits to combinatorial circuits using unrolling techniques was known and it was applied to a different context of traditional simulation in U.S. Pat. No. 5,752,000 to McGeer et al (1998). The unrolling techniques are well known to those skilled in the art for limited applications in ATPG, but they are generally not used for synthesis because the equivalence between the digital circuits and the combinational circuits is true only if the number of clock cycles being considered is below a given limit.
Equivalence checking between combinatorial circuits was known, and it was applied to a different and restricted form of digital circuit verification in U.S. Pat. No. 5,754,454 to Pixley et al (1998), where the complete equivalence between two digital circuits were to be proven. ATPG techniques for combinational circuits are known to be useful within this kind of equivalence checking.
The present invention provides a method for verifying a digital circuit design in a hardware description language, using a verification structure and a verification engine. The verification structure is constructed by including a design under test and additional statements in the hardware description language so that the functional verification problem becomes whether the verification structure is equivalent to a predetermined constant. These additional statements are provided to describe input constraints and behavioral expectations, and they effectively describe a test bench with a group of test cases. The verification engine automatically gives a conclusion after analyzing the verification structure as a digital circuit design. The functional correctness of the design can be completely verified using a number of verification structures.
The objects and advantages of this invention are to provide functional verification methods that
(a) are efficient due to high coverage in each run,
(b) work well for large circuit designs because of avoiding a big bottleneck step, and
(c) do not require any language in addition to a hardware description language.
Further objects and advantages of this invention will become apparent from a consideration of the drawings and ensuing description.